package Algorithm.dynamicProgramming.swordOffer;

/**
 * 剑指 Offer 46. 把数字翻译成字符串 https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
 */
public class TranslateNum {

    /**
     * 思路一：
     * 动态规划 n为数的翻译方法为 前n-1位 + 前n-2位翻译方法数（若最后两位可翻译）
     * 1. 定义dp：dp[i]为[0, i]位数的翻译方法数
     * 2. 状态转移公式：若[i-1,i]构成的两位数小于26，则dp[i] = dp[i-1] + dp[i-2]
     *                  否则dp[i] = dp[i-1]
     * 3. 初始化：dp[0] = 1
     */
    public int translateNum(int num) {
        String s = num + "";
        int[] dp = new int[s.length()];
        dp[0] = 1;
        for (int i = 1;i < s.length();i++) {
            String str = s.substring(i-1, i+1);
            //若最后两位可翻译则dp[i] = dp[i-1] + dp[i-2];
            if (!str.startsWith("0") && Integer.parseInt(str) < 26) {
                if (i == 1) dp[i] = 2;
                else dp[i] = dp[i-1] + dp[i-2];
            } else dp[i] = dp[i-1];
        }
        return dp[s.length()-1];
    }


    /**
     * 思路二：回溯算法。路径选择列表：begin开头的子串[begin, i]
     */
    int count;
    public int translateNum2(int num) {
        String s = num + "";
        backTracing(s, 0, s.length());
        return count;
    }
    public void backTracing(String s, int begin, int n) {
        //终止条件：当全部划分完毕，count增1然后返回
        if (begin == n) {
            count++;
            return;
        }
        //路径选择列表：begin开头的子串[begin, i]
        for (int i = begin;i < n && i <= begin+1;i++) {
            //剪枝：子串长度小于等于2，且长度为2的子串不能以0开头 且不大于25
            if (i > begin && s.charAt(begin) == '0') continue;
            int v = Integer.parseInt(s.substring(begin, i+1));
            if (v > 25) continue;
            //下一步路径选择列表：i+1开头的子串
            backTracing(s, i+1, n);
        }
    }
}
